轉眼間,來到第十天了!今天這一題是一個和進位法換算相關的題目,會運用到一些ASCII的技巧,是相當有趣的一題,讓我們一起來看看吧!
Given a string columnTitle that represents the column title as appear in an Excel sheet, return its corresponding column number.
For example:
A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28
...
Example 1:
Input: columnTitle = "A"
Output: 1Example 2:
Input: columnTitle = "AB"
Output: 28Example 3:
Input: columnTitle = "ZY"
Output: 701Example 4:
Input: columnTitle = "FXSHRXW"
Output: 2147483647
這題的希望我們做的就是將26進位表示法的整數轉換成十進制,這邊的26進位比較特別的是前十個並不是用數字來表示,而是英文大寫字母A-Z,所以我們要回傳的就是相對應的整數。
根據進位法的定義,我們可以得知十進位中的個位數是「在個位的數字10的0次方」、十位數是「十位數字10的1次方」依此類推,在二十六進制中也是相同的道理,個位數是「在個位的數字26的0次方」、十位數是「十位數字26的1次方」......,OK 那我們就可以用這個邏輯去做這一題。
可是重點來了,我們要怎麼知道A代表1,Z代表26,在起初我做這題的時候,是想到建立一個陣列或是HashMap,使其能夠一一對應,但後來突然想到,對電腦來說字母其實也是數字,也就是所謂的ASCII Code,那為何不用這個特性來達到A-Z => 1~26 的轉換,只要將A(ASCII中的65)轉換成整數並減去64,就變成1了,其餘的也一一對應,因此在我的算法中,的確就是使用到ASCII Code與for迴圈,按照定義將結果累加出來並回傳。
以下是python3的程式碼
class Solution:
def titleToNumber(self, columnTitle: str) -> int:
total = 0
for i, v in enumerate(columnTitle[::-1]):
total += (ord(v)-64) * (26 ** i) # ASCII轉換成數字
return total
以下是C++的程式碼
class Solution {
public:
int titleToNumber(string columnTitle) {
int count=0;
int size = columnTitle.size();
for(int i=0;i<size;i++){
int o = columnTitle[size-(i+1)];
count += (o-64) * (pow(26, i));
}
return count;
}
};
以下也是C++的程式碼,但這個方法通過了優化迴圈進行方式,來達到不需要呼叫指數函式,會更節省空間與加強效率。
class Solution {
public:
int colCharToInt( char ch ) {
return ( ch - 'A' + 1 );
}
int titleToNumber(string columnTitle) {
int currNum = 0;
for( int i = 0; i < columnTitle.size(); i++ ) {
int currVal = colCharToInt( columnTitle[i] );
currNum = currNum * 26 + currVal;
}
return currNum;
}
};